La chiesa è stata costruita sul luogo dove il governatore Publio avrebbe incontrato San Paolo dopo il naufragio sulle coste dell'isola di Malta della nave che lo trasportava a Roma. L'aggregato monumentale sulla spianata e nelle immediate adiacenze comprende l'Arcivescovado del 1642, il Seminario oggi adibito a Museo, il Tribunale del 1620 e il Palazzo del Governatore di Gozo.

 

Secondo la tradizione, il sito era originariamente occupato dal palazzo appartenente a Publio, governatore romano della Melita, funzionario che ha accolto l'apostolo Paolo naufragato sulle coste dell'arcipelago maltese. Infatti l'apostolo come cittadino romano, dopo aver predicato in Giudea, esser stato imprigionato in Cesarea, fu dal governatore Porcio Festo consegnato al centurione Giulio per essere condotto a Roma e subire il processo di eresia al cospetto dell'imperatore Nerone. La nave che lo trasportava assieme a Luca, Aristarco, Trofimo e ad altri 261 passeggeri, dopo una terribile tempesta al largo dell'isola di Creta, approdò fortunatamente presso la località maltese denominata Isole di San Paolo nell'anno 58 d.C. Sul luogo dello sbarco, una statua ne commemora l'evento.

 

San Paolo inizialmente trovò rifugio in una grotta, ambiente oggi conosciuto come le Catacombe di San Paolo a Rabat. Allo scampato pericolo e al fortuito scalo, altri eventi inspiegabili segnarono la breve permanenza dell'apostolo, fra essi il morso di una vipera senza ulteriori gravi conseguenze. La narrazione di Luca evangelista negli Atti degli Apostoli, cita Paolo quale guaritore del padre del rappresentante locale, sofferente di febbre e dissenteria, e di molti altri ammalati sull'isola. Gli isolani interpretarono questa sequenza di episodi come un segno ultraterreno di un personaggio carismatico, trascinatore e persuasivo. Questi avvenimenti sono alla base della grande fede che indusse la popolazione alla conversione al cristianesimo, al punto che lo stesso Publio divenne un fervente seguace e primo vescovo di Malta.

 

Il primo tempio dedicato alla Beata Vergine Maria, cadde in rovina durante il periodo arabo con il saccheggio sistematico dei luoghi di culto a seguito dell'invasione degli aghlabidi nell'870.

 

In seguito alla riconquista normanna nel 1091, fu ristabilito il cristianesimo nelle isole maltesi. La primitiva cattedrale violata e semidistrutta fu riedificata in stile gotico-romanico e dedicata a San Paolo.

 

Le strutture del tempio subiscono un primo ampliamento nel 1420, le volte sono affrescate da un pittore siciliano con raffigurazioni tratte da episodi del Vecchio e Nuovo Testamento.

 

Nel 1679, il vescovo Miguel Jerónimo de Molina y Aragonés e il capitolo della cattedrale decisero di ammodernare il coro e l'abside medievali con altrettanti manufatti in stile barocco, affidando la progettazione e la supervisione della costruzione all'architetto Lorenzo Gafà. Prima del terremoto del 1693 sono documentate: la Cappella della Santissima Trinità, la Cappella San Michele, la Cappella di San Giovanni Battista con un dipinto raffigurante la decollazione del precursore, la Cappella dell'Annunciazione col primitivo dipinto di Mattia Preti, la Cappella di San Michele e la Cappella della Vergine di Monserrat adiacenti sulla parete settentrionale, la Cappella dell'Assunta, la Cappella di San Pietro, la Cappella dell'Angelo Custode e altri ambienti dedicati a santi richiamati nell'attuale esposizione iconografica delle pitture quali San Giuseppe Patriarca, San Filippo Neri, San Gaetano, San Nicola di Bari.

 

La serie di scosse del terremoto del Val di Noto nel 1693, evento sismico che interessò gran parte della Sicilia orientale e un'ampia area del bacino del mar Mediterraneo, scombinò i programmi. Gravemente danneggiata l'11 aprile 1693, fu concorde la decisione di smantellare la vecchia cattedrale e ricostruirla in stile barocco sempre su progetto di Gafà. Il coro e la sacrestia, scampati alla distruzione, furono inglobati nella nuova costruzione. I lavori iniziarono nel 1696, e l'edificio fu quasi completato nel 1702.

 

Numerose opere scamparono alla rovina: il dipinto del pittore calabrese Mattia Preti raffigurate la Conversione di San Paolo sulla via di Damasco, un ciclo di cinque tele del medesimo autore, il dipinto toscano Madonna con Bambino e gli affreschi dell'abside che illustrano le sequenze del naufragio di San Paolo e il suo arrivo nell'arcipelago.

 

La solenne consacrazione presieduta dal vescovo Davide Cocco Palmeri avvenne l'8 ottobre 1702. Il complesso fu terminato il 24 ottobre 1705 con il completamento della cupola. L'intero edificio è considerato un capolavoro di Lorenzo Gafà.

 

Nel 1720 alcune abitazioni medievali furono demolite per erigere il Palazzo Vescovile, il Seminario (odierno Museo della Cattedrale) e la piazza antistante. Col terremoto del 26 febbraio 1743 si verificò il crollo della lanterna, prontamente ricostruita nel 1747.

 

La supremazia politico-economica di La Valletta su tutte le città maltesi, congiuntamente alla notevole influenza dei gran maestri dell'Ordine dei Cavalieri Ospitalieri presso la curia romana, determinò la condivisione del titolo con la concattedrale di San Giovanni.

 

L'edificio fu danneggiato dal terremoto del 12 ottobre 1856, la cupola fu distrutta comportando la perdita degli affreschi della calotta, opere dei fratelli Manno.

 

Oggi, l'aggregato monumentale è una delle principali attrazioni turistiche di Mdina, è dichiarato monumento nazionale ed è elencato nell'inventario nazionale dei beni culturali delle isole maltesi.